//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 
//
// 
//
// 示例 1： 
//
// 输入：head = [1,3,2]
//输出：[2,3,1] 
//
// 
//
// 限制： 
//
// 0 <= 链表长度 <= 10000 
// Related Topics 栈 递归 链表 双指针 👍 290 👎 0

package leetcode.editor.offer;

import java.util.*;

// 剑指 Offer 06. 从尾到头打印链表
class CongWeiDaoTouDaYinLianBiaoLcof {
    public static void main(String[] args) {
        Solution solution = new CongWeiDaoTouDaYinLianBiaoLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    Definition for singly-
//    linked list.

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution {
        /**
         * 暴力反序法
         *
         * @param head
         * @return
         */
//        public int[] reversePrint(ListNode head) {
//            ListNode cur = head;
//            List<Integer> list = new ArrayList<>();
//            while (cur != null) {
//                list.add(cur.val);
//                cur = cur.next;
//            }
//
//            Collections.reverse(list);
//            int[] res = new int[list.size()];
//            for (int i = 0; i < list.size(); i++) {
//                res[i] = list.get(i);
//            }
//            return res;
//        }
//

        // 递归法
        // 时间复杂度 O(N)O(N)： 遍历链表，递归 NN 次。
        // 空间复杂度 O(N)O(N)： 系统递归需要使用 O(N)O(N) 的栈空间。
//        public int[] reversePrint(ListNode head) {
//            recur(head);
//            int[] res = new int[list.size()];
//            for (int i = 0; i < res.length; i++) {
//                res[i] = list.get(i);
//            }
//            return res;
//        }
//
//        List<Integer> list = new ArrayList<>();
//
//        public void recur(ListNode node) {
//            if (node == null) {
//                return;
//            }
//            recur(node.next);    // 先递归到最后节点
//            list.add(node.val); // 回溯，加入此节点值
//        }

        // 利用栈的特性
        // 时间复杂度 O(N)O(N)： 入栈和出栈共使用 O(N)O(N) 时间。
        // 空间复杂度 O(N)O(N)： 辅助栈 stack 和数组 res 共使用 O(N)O(N) 的额外空间。
        public int[] reversePrint(ListNode head) {
            Stack<Integer> stack = new Stack<Integer>();
            while (head != null) {
                stack.push(head.val);
                head = head.next;
            }
            int[] res = new int[stack.size()];
            for (int i = 0; i < res.length; i++) {
                res[i] = stack.pop();
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
